﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Algoritmia.DataStructures.Queues;
using Algoritmia.DataStructures.Trees;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Traversals
{
    public class PreorderTreeTraverser<TNode,TResult> : ITreeTraverser<TNode,TResult>
    {
        private readonly Func<ILifo<IRootedTree<TNode>>> _createLifo;

        public PreorderTreeTraverser(Func<ILifo<IRootedTree<TNode>>> createLifo = null)
        {
            _createLifo = createLifo ?? ( () => AlgoritmiaFactory.Lifos<IRootedTree<TNode>>.Default);
        }

        #region ITreeTraverser<TNode,TResult> Members

        public IEnumerable<TResult> Traverse(IRootedTree<TNode> tree, Func<IRootedTree<TNode>, TResult> visitor = null)
        {
            var stack = _createLifo();
            visitor = visitor ?? (subtree => (TResult)(object)subtree.Root);
            stack.Push(tree);

            while( stack.Count > 0)
            {
                IRootedTree<TNode> currentTree = stack.Pop();
                yield return visitor(currentTree);
                foreach(var subtree in currentTree.SubTrees().Reverse())
                {
                    stack.Push(subtree);
                }
            }
        }

        #endregion
    }
}
